<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
Search and Optimisation Support
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial049.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial046.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial051.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc107">7.4</A>&nbsp;&nbsp;Search and Optimisation Support</H2><UL>
<LI><A HREF="tutorial050.html#toc59">Tree Search Methods: <EM>ic_search</EM></A>
<LI><A HREF="tutorial050.html#toc60">Optimisation: <EM>branch_and_bound</EM></A>
</UL>


<A NAME="toc59"></A>
<H3 CLASS="subsection"><A NAME="htoc108">7.4.1</A>&nbsp;&nbsp;Tree Search Methods: <EM>ic_search</EM></H3>
<A NAME="@default178"></A>
<A NAME="shortsecsearch"></A>
ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> has built-in backtracking and is therefore well suited for
performing depth-first tree search.
With combinatorial problems, naive depth-first search is usually not
good enough, even in the presence of constraint propagation.
It is usually necessary to apply heuristics, and if the problems are
large, one may even need to resort to incomplete search.
The <EM>ic_search</EM> contains a collection of predefined, easy-to-use
search heuristics as well as incomplete tree search strategies, applicable
to problems involving <EM>ic</EM> variables.
For more details see chapter <A HREF="tutorial086.html#chapsearch">12</A>.<BR>
<BR>
<A NAME="toc60"></A>
<H3 CLASS="subsection"><A NAME="htoc109">7.4.2</A>&nbsp;&nbsp;Optimisation: <EM>branch_and_bound</EM></H3>
<A NAME="@default179"></A>
<A NAME="shortsecbb"></A>
Solvers that are based on constraint propagation are typically only
concerned with satisfiability, i.e. with finding some or all solutions
to a problems.
The branch-and-bound method is a general technique to build optimisation
on top of a satisfiability solver.
The ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> <EM>branch_and_bound</EM> library is a solver-independent
implementation of the branch-and-bound method, and provides a number
of options and variants of the basic technique.<BR>
<BR>
<HR>
<A HREF="tutorial049.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial046.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial051.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
